package hu.arguscab.ai;


import hu.arguscab.ai.util.QuadNode;

import java.util.HashMap;
import java.util.Map;

public class QuadTree<E, N> extends TreeImpl<E, N> {

	public static final int A = 0;
	public static final int B = 1;
	public static final int C = 2;
	public static final int D = 3;
	
	enum Quadrant {
		A, B, C, D;
		
		private static final Quadrant[][] dirSides = {{A, B},	// North
			 {C, D},	// South
			 {B, D},	// East
			 {A, C}};	// West

		public static Quadrant[] get(Dir dir) {
			return dirSides[dir.ordinal()];
		}

		public static boolean isNeightbor(Quadrant dirA, Quadrant dirB) {
			return Dir.getStrictDir(dirA, dirB) != null;
		}
	}
	
	enum Dir {
		NORTH, SOUTH, EAST, WEST;
		
		// csak akkor szomszéd, ha egy szitnen vannak
		static private Dir[][] strictDirs = {
			{null, EAST, SOUTH, null},		// A
			{WEST, null, null, SOUTH},		// B
			{NORTH, null, null, EAST},		// C
			{null, NORTH, WEST, null},		// D
		};
		
		// ez csak az irányt mondja meg, pl A->D East
		static private Dir[][] dirs = {
			{null, EAST, SOUTH, EAST},		// A
			{WEST, null, WEST, SOUTH},		// B
			{NORTH, EAST, null, EAST},		// C
			{WEST, NORTH, WEST, null},		// D
		};
		
		public Dir opposite() {
			switch(this) {
				case NORTH:
					return SOUTH;
				case SOUTH:
					return NORTH;
				case EAST:
					return WEST;
				case WEST:
					return EAST;
			}
			return null;
		}
		
		static public Dir getDir( Quadrant a, Quadrant b ) {
			return dirs[a.ordinal()][b.ordinal()];
		}
		
		static public Dir getStrictDir( Quadrant a, Quadrant b ) {
			return strictDirs[a.ordinal()][b.ordinal()];
		}
	}
	
	/**
	 * Elements must be the same order as in Dir enum was ordered.
	 */
	private static final int[][] dirSides = {{A, B},	// North
											 {C, D},	// South
											 {B, D},	// East
											 {A, C}};	// West
	
	private QuadNode<N> root;
	private QuadNode<N>[] firstLevel;
	private Map<QuadNode<N>, QuadNode<N>[]> childMap = new HashMap<QuadNode<N>, QuadNode<N>[]>();
	private Map<QuadNode<N>, QuadNode<N>> parentMap = new HashMap<QuadNode<N>, QuadNode<N>>();
	
	private Graph<E, N> currentGraph;
	private Node<N> aNodeInGraph;		// csak kell egy nodem, ami benne van a gráfban
	
	private void method2(QuadNode<N> a, QuadNode<N> b, Dir dir, Quadrant dirA, Quadrant dirB, int depthA, int depthB) {
		if ( depthA == depthB && Quadrant.isNeightbor(dirA, dirB) == false )
			return;
		
		// Ha egy szinten vannak, vagy B-nek nincs gyermeke, de A-nak még van
		if ( (depthA == depthB || hasChild(b)==false) && hasChild(a) ) {
			QuadNode<N>[] childs = childArray(a);
			
			method2(childs[A], childs[B], Dir.EAST, Quadrant.A, Quadrant.B, 0, 0);
			method2(childs[A], childs[C], Dir.SOUTH, Quadrant.A, Quadrant.C, 0, 0);
			method2(childs[B], childs[D], Dir.SOUTH, Quadrant.B, Quadrant.D, 0, 0);
			method2(childs[C], childs[D], Dir.EAST, Quadrant.C, Quadrant.D, 0, 0);
			
			Quadrant[] qs = Quadrant.get(dir);
			int[] indices = dirSides[dir.ordinal()];
			method2(childs[ indices[0] ], b, dir, qs[0], dirB, depthA + 1, depthB);
			method2(childs[ indices[1] ], b, dir, qs[1], dirB, depthA + 1, depthB);
			return;
		} else if ( hasChild(b) ) {
			QuadNode<N>[] childs = childArray(b);
			
			method2(childs[A], childs[B], Dir.EAST, Quadrant.A, Quadrant.B, 0, 0);
			method2(childs[A], childs[C], Dir.SOUTH, Quadrant.A, Quadrant.C, 0, 0);
			method2(childs[B], childs[D], Dir.SOUTH, Quadrant.B, Quadrant.D, 0, 0);
			method2(childs[C], childs[D], Dir.EAST, Quadrant.C, Quadrant.D, 0, 0);
			
			Quadrant[] qs = Quadrant.get(dir.opposite());
			int[] indices = dirSides[dir.opposite().ordinal()];
			method2(a, childs[ indices[0] ], dir, dirA, qs[0], depthA, depthB+1);
			method2(a, childs[ indices[1] ], dir, dirA, qs[1], depthA, depthB+1);
			return;
		}
		assert(a != null);
		assert(b != null);
		
		join(a, b);
	}
	
	private void join(QuadNode<N> a, QuadNode<N> b) {
		if ( hasChild(a) == false && hasChild(b) == false ) {
			float dist = a.getCenter().getDistanceFrom(b.getCenter());
			// 	Creating Edge with weight
			Edge<E> e = new Edge<E>();
			e.setWeight((int) dist);
			currentGraph.addNode(a, b, e);
			aNodeInGraph = a;		
		}
	}
	
	public Node<N> createGraph(Graph<E, N> graph) {
		currentGraph =  graph;
		if ( firstLevel[A] == null )
			return null;
		
		method2(firstLevel[A], firstLevel[B], Dir.EAST, Quadrant.A, Quadrant.B, 0, 0);
		method2(firstLevel[A], firstLevel[C], Dir.SOUTH, Quadrant.A, Quadrant.C, 0, 0);
		method2(firstLevel[B], firstLevel[D], Dir.SOUTH, Quadrant.B, Quadrant.D, 0, 0);
		method2(firstLevel[C], firstLevel[D], Dir.EAST, Quadrant.C, Quadrant.D, 0, 0);
		return aNodeInGraph;
	}
	
	public QuadNode<N>[] childArray(Node<N> node) {
		return childMap.get(node);
	}
	
	@Override
	public Iterable<Node<N>> breathSearchIterator() {
		// TODO Auto-generated method stub
		return null;
	}

	@Override
	public Iterable<Node<N>> childs(Node<N> node) {
		// TODO Auto-generated method stub
		return null;
	}
	
	@Override
	public void clear() {
		childMap.clear();
	}

	@Override
	public Iterable<Node<N>> depthSearchIterator() {
		// TODO Auto-generated method stub
		return null;
	}

	@Override
	public Node<N> getParent(Node<N> node) {
		return parentMap.get(node);
	}

	@Override
	public boolean hasChild(Node<N> n) {
		QuadNode<N>[] c = childMap.get(n);
		return c != null && (c[0] != null);
	}

	@Override
	public Iterable<Node<N>> leafFirstIterator() {
		// TODO Auto-generated method stub
		return null;
	}

	public void addNode(QuadNode<N> from, QuadNode<N> newNode, Edge<E> edge, int i) {
		if ( containsNode(from) == false )
			addNode(from);
		
		if ( containsNode(newNode) == false )
			addNode(newNode);
		
		childMap.get(from)[i] = newNode; 
		parentMap.put(newNode, from);
	}

	private void addNode(QuadNode<N> newNode) {
		childMap.put(newNode, new QuadNode[4]);
	}

	@Override
	public Iterable<Node<N>> adjacentTo(Node<N> node) {
		// TODO Auto-generated method stub
		return null;
	}

	@Override
	public boolean containsEdge(Node<N> from, Node<N> to) {
		// TODO Auto-generated method stub
		return false;
	}

	@Override
	public boolean containsNode(Node<N> node) {
		return childMap.get(node) != null;
	}

	@Override
	public int degree(Node<N> node) {
		// TODO Auto-generated method stub
		return 0;
	}

	@Override
	public void deleteNode(Node<N> node) {
		// TODO Auto-generated method stub
		
	}

	@Override
	public Edge<E> getEdge(Node<N> from, Node<N> to) {
		// TODO Auto-generated method stub
		return null;
	}

	@Override
	public QuadNode<N> getRoot() {
		return root;
	}

	@Override
	public Node<N> setRoot(N rootObject) {
		return null;
	}

	public void setRoot(QuadNode<N> root) {
		this.root = root;
		addNode(root);
		firstLevel = childArray(root);
	} 
	
	@Override
	public String toString() {
		StringBuilder sb = new StringBuilder();
		for ( Node<N> node : breathSearchIterator() ) {
			sb.append(node).append(", ");
		}
		return sb.toString();
	}

}